package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 918. 环形子数组的最大和
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/23 22:06
 */
public class MaxSubarraySumCircular {

    public static void main(String[] args) {
        MaxSubarraySumCircular test = new MaxSubarraySumCircular();

        // 3
//        int[] arr = {1,-2,3,-2};

        // 10
//        int[] arr = {5,-3,5};

        // 4
//        int[] arr = {3,-1,2,-1};

        // 3
//        int[] arr = {3,-2,2,-3};

        // -1
//        int[] arr = {-2, -3, -1};

        int[] arr = {52,183,124,154,-170,-191,-240,107,-178,171,75,186,-125,61,-298,284,21,-73,-294,253,146,248,-248,127,26,289,118,-22,-300,26,-116,-113,-44,29,252,-278,47,254,-106,246,-275,42,257,15,96,-298,-69,-104,-239,-95,-4,76,-202,156,-14,-178,188,-84,78,-195,-125,28,109,125,-25,-53,58,287,55,-296,198,281,53,-160,146,298,25,-41,-3,27,-242,169,287,-281,19,91,213,115,211,-218,124,-25,-272,278,296,-177,-166,-192,97,-49,-25,168,-81,6,-94,267,293,146,-1,-258,256,283,-156,197,28,78,267,-151,-230,-66,100,-94,-66,-123,121,-214,-182,187,65,-186,215,273,243,-99,-76,178,59,190,279,300,217,67,-117,170,163,153,-37,-147,-251,296,-176,117,68,258,-159,-300,-36,-91,-60,195,-293,-116,208,175,-100,-97,188,79,-270,80,100,211,112,264,-217,-142,5,105,171,-264,-247,138,275,227,-86,30,-219,153,10,-66,267,22,-56,-70,-234,-66,89,182,110,-146,162,-48,-201,-240,-225,-15,-275,129,-117,28,150,84,-264,249,-85,70,-140,-259,26,162,5,-203,143,184,101,140,207,131,177,274,-178,-79,14,-36,104,52,31,257,273,-52,74,276,104,-133,-255,188,-252,229,200,-74,-39,-250,142,-201,-196,-43,-40,255,-149,-299,-197,-175,-96,-155,-196,-24,12,79,71,-144,-59,-120,227,-256,-163,-297,116,286,-283,-31,-221,-41,121,-170,160,205,8,88,25,-272,-107,292,-180,299,94,-97,-81,-134,37,238};

        // 1458
//        int[] arr = {52,183,124,154,-170,-191,-240,107,-178,171,75,186,-125,61,-298,284,21,-73,-294,253,146,248,-248,127,26,289,118,-22};

        int i = test.maxSubarraySumCircular(arr);
        System.out.println(i);
    }

    public int maxSubarraySumCircular(int[] nums) {
        int length = nums.length;
        int l = length << 1;
        int[] arr = new int[l];
        System.arraycopy(nums, 0, arr, 0, length);
        System.arraycopy(nums, 0, arr, length, length);
        int max = arr[0];
        int item = arr[0];
        int end = 0;
        for (int i = 1; i < l; i++) {
            if (i - end == length) {
                int m = arr[i - 1];
                int k = i - 1;
                int s = m;
                for (int j = i - 2; j > end; j--) {
                    s += arr[j];
                    if (s  > m) {
                        m = s ;
                        k = j;
                    }
                }
                end = k;
                item = m;

            }
            if (item + arr[i] > arr[i]) {
                item += arr[i];
            } else {
                item = arr[i];
                end = i;
            }
            max = Math.max(max, item);
        }
        return max;
    }

    public int maxSubarraySumCircular2(int[] A) {
        if (A == null || A.length < 1) {
            return 0;
        }
        int curMax, max, curMin, min, sum;
        curMax  = max = curMin = min = sum = A[0];
        for (int i = 1; i < A.length; i++) {
            sum += A[i];
            curMax = curMax > 0 ? curMax + A[i] : A[i];
            max = curMax > max ? curMax : max;
            curMin = curMin < 0 ? curMin + A[i] : A[i];
            min = curMin < min ? curMin : min;
        }
        if (max < 0) {
            return max;
        }
        return Math.max(sum - min, max);
    }

}
